import numpy as np

# 定义函数
def f(x):
    return x**5 + 4*x**3 + 5

# 计算离散傅里叶变换（DFT）
def DFT(x):
    N = len(x)
    X = np.zeros(N, dtype=np.complex128)
    for k in range(N):
        X[k] = sum(x[n] * np.exp(-2j * np.pi * k * n / N) for n in range(N))
    return X

# 使用 FFT 计算离散傅里叶变换
def FFT(x):
    N = len(x)
    if N <= 1:
        return x
    even = FFT(x[0::2])
    odd = FFT(x[1::2])
    T = [np.exp(-2j * np.pi * k / N) * odd[k] for k in range(N // 2)]
    return [even[k] + T[k] for k in range(N // 2)] + [even[k] - T[k] for k in range(N // 2)]

# 选择离散的 x 值
N = 64  # 选择样本点的数量
x_values = np.linspace(-5, 5, N)  # 在区间[-5, 5]中选择 N 个点
y_values = f(x_values)  # 计算函数值

# 使用手动实现的 FFT 计算离散傅里叶变换
fft_y = FFT(y_values)

# 使用逆变换将离散傅里叶变换转换回原始函数形式
approximation = np.fft.ifft(fft_y)

# 输出逼近结果
print("逼近结果：", approximation)
